package sliding_window;

public class minWindow {
    public String minWindow(String s, String t) {
        String ret = null;
        int[] hash1 = new int[128];//记录t中的各个字符出现的数量
        int kinds = 0;//统计t的字符的种类，不统计个数
        for(int i = 0; i < t.length();i++) {
            if(hash1[t.charAt(i)-'A']++ == 0) kinds++;
        }

        int[] hash2 = new int[128];//用于记录left -> right 中各个字符的数量
        int count = 0;//统计left -> right 中满足t中字符的种类
        int min = Integer.MAX_VALUE;//用于记录覆盖子串的大小

        int left = 0,right = 0;
        while(right < s.length()){
            //进窗口+维护count
            hash2[s.charAt(right)-'A']++;
            if(hash2[s.charAt(right)-'A'] == hash1[s.charAt(right)-'A']) {
                count++;
            }

            while(count == kinds){//判断条件
                //更新结果
                if(min > right-left+1) {
                    min = right-left+1;
                    ret = s.substring(left,right+1);
                }
                //出窗口 + 维护count
                if(hash2[s.charAt(left)-'A'] == hash1[s.charAt(left)-'A']) {
                    count--;
                }
                hash2[s.charAt(left)-'A']--;
                left++;

            }
            right++;
        }
        return min == Integer.MAX_VALUE ? "": ret;

    }
}
